package leetcode_core.leetcode_1;

public class BackPackPro {

    public int backPack(int W,int N,int[] wt,int[] val){
        //1.定义dp数组,dp[i][w]是指对于前i个物品,当前背包容量为w,这时候所能得到的最大价值
        //要确定数组的大小,必须确定最终的答案:dp[N][W]
        int[][] dp = new int[N+1][W+1];
        //2.写出base-case,当i或者w有其中有一个等于0的时候,这个值就是0
        dp[0][0] = 0 ;
        for(int i = 1;i <= N;i++){
            dp[i][0] = 0;
        }
        for(int w = 1;w <= W ; w++){
            dp[0][w] = 0;
        }
        //3.写出状态转移方程
        //3.1 确定遍历顺序:根据DP-table,容易知道,此时Dp-table被初始化为第0列为0,第0行为0的一个正方形表
        //3.1 根据状态转移方程,容易知道,我们希望得到的是这个元素的左上角已经被全部计算完了,因此遍历顺序是顺序遍历的(可以画图验证)
        for(int i = 1; i <= N;i++){
            for(int j = 1; j <= W;j++){
                //现在试图装第i-1个物品
                if(j-wt[i-1]<0){//如果现在装不下,那么只能选择不装进背包
                    dp[i][j] = dp[i-1][j];
                }else{//否则就是可以装下背包,有选择的余地
                    dp[i][j] = Math.max(
                            dp[i-1][j],//选择不装入背包,继承不装这个东西进背包,但容量保持这么多的
                            dp[i-1][j-wt[j]]+val[i-1]//选择装入背包
                    );
                }
            }
        }
        return dp[N][W];
    }
}
